package com.lga.dataStructure;


/**
 *describe: 自定义的单链表
 *
 *@author lga
 *@date  2019/12/7 0007 21:00
 */

public class SingleLinkedList {

    //空的头结点
    private Node head = new Node(null,null);
    //单链表的长度
    private int size = 0;

    public SingleLinkedList(Node node) {
        this.head = node;
        while (node.next!=null) {
            node = node.next;
            this.size++;
        }

    }

    public SingleLinkedList(Object[] datas) {
        Node p = head;
        for (int i = 0; i < datas.length; i++) {
            Node newNode = new Node(datas[i],null);
            while (p.next != null) {
                p = p.next;
            }
            p.next = newNode;
            size++;
        }
    }

    /**
     * 新增节点到尾部
     * @param newNode
     */
    public void addToTail(Object data) {
        Node newNode = new Node(data, null);
        Node p = head;
        while (p != null && p.next != null) {
            p = p.next;
        }
        newNode.next = p.next;
        p.next = newNode;
        size++;
    }

    /**
     * 新增节点到头部
     */
    public void addToHead(Object data) {
        Node newNode = new Node(data,null);
        newNode.next = head.next;
        head.next = newNode;
        size++;
    }

    /**
     * 新增节点到指定的位置
     */
    public void addToPosition(Object data, int position) {
        Node newNode = new Node(data,null);
        Node p = head;
        int tempPosition = 1;
        if (size < position) {
            new IllegalArgumentException("需要插入的节点超出了链表的最大的位置");
        }
        while (position != tempPosition++) {
            p = p.next;
        }

        newNode.next = p.next;
        p.next = newNode;
        size++;
    }


    /**
     * 删除节点
     * @param position
     */
    public void remove(int position) {
        int tempPosition = 1;
        Node p = head;
        if (position > size) {
            new IllegalArgumentException("需要删除的位置超出了单链表的最大长度");
        }
        while (position != tempPosition++) {
            p = p.next;
        }
        p.next = p.next.next;
        size--;
    }

    /**
     * 更新数据
     * @param newData
     * @param position
     * @return
     */
    public boolean update(Object newData, int position) {
        int tempPosition = 0;
        Node p = head;
        if (position > size) {
            return false;
        }
        while (position != tempPosition++) {
            p = p.next;
        }
        p.setData(newData);
        return true;
    }

    /**
     * 通过位置获取节点的数据
     * @param position
     * @return
     */
    public Object get(int position) {
        int tempPosition = 0;
        Node p = head;
        if (position > size) {
            return null;
        }
        while (position != tempPosition++) {
            p = p.next;
        }
        return p.getData();
    }

    /**
     * 倒转单链表
     * @return
     */
    public SingleLinkedList reverse() {
        Node q = new Node(null,null);
        Node p = head.next;
        Node next = null;
        while (p != null ) {
            next = p.next;
            p.next = q.next;
            q.next = p;
            p = next;
        }
        return new SingleLinkedList(q);
    }

    /**
     * 获取节点的大小
     */
    public int getSize() {
        return this.size;
    }

    /**
     * 打印所有节点
     */
    public void printAllNode() {
        Node p = head;
        while (p.next != null) {
            p = p.next;
            System.out.print(p.data+" ");
        }
    }


    /**
     *
     */

    public static void main(String[] args) {

        SingleLinkedList singleLinkedList = new SingleLinkedList(new String[]{"a","b","c","d"});
        //singleLinkedList.addToTail(1);
        //singleLinkedList.addToTail(2);
        //singleLinkedList.addToTail(3);
        //singleLinkedList.addToTail(4);
        //singleLinkedList.addToHead(5);
        //singleLinkedList.addToPosition(10,3);
        //singleLinkedList.remove(6);
        //System.out.println("打印所有的单链表节点");
        //singleLinkedList.printAllNode();
        //System.out.println();
        //System.out.println("单链表的长度为:");
        //System.out.println(singleLinkedList.getSize());
        //
        //System.out.println("修改数据");
        //singleLinkedList.update("woshishei", 4);
        //System.out.println("打印所有的单链表节点");
        //singleLinkedList.printAllNode();
        //
        //System.out.println("查数据");
        //System.out.println(singleLinkedList.get(4));

        System.out.println("倒转单链表");
        singleLinkedList.reverse().printAllNode();

    }

    /**
     * 节点Node
     */
    private class Node{
        private Object data;
        private Node next;

        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
        public Object getData() {
            return data;
        }

        public void setData(Object data) {
            this.data = data;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }



}
